/**
 * @author:gao
 * @date:2020/6/9
 * @time:11:40
 * @version:0.0.1
 * @description:none
 */

public class fatfeng {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.translateNum(604);
    }
}
//面试题46 dp 并且【可以优化】
class Solution {

    public int translateNum(int num) {
        String s = String.valueOf(num);
        if(s.length()==1)return 1;
        int len = s.length();
        int[] dp = new int[len];
        dp[len-1] = 1;
        if(s.charAt(len-2)!='0'&&Integer.parseInt(s.substring(len-2,len))<26){
            dp[len-2]=2;
        }else{
            dp[len-2]=1;
        }
        for(int i=len-3;i>=0;i--){
            if(s.charAt(i)!='0'&&Integer.parseInt(s.substring(i,i+2))<26){
                dp[i]=dp[i+1]+dp[i+2]; //可以看出，每个dp[i]只跟它后面得两个有关，
                                        //所以可以不申请空间，直接用变量循环迭代
            }else{
                dp[i]=dp[i+1];
            }
        }
        return dp[0];
    }

}